Σχέση Ισοδυναμίας
Σχέσις Ισοδυναμίας Equivalence_relation - Είναι μία Μαθηματική Σχέση. Ετυμολογία Η ονομασία "σχέση ισοδυναμίας" σχετίζεται ετυμολογικά με την λέξη "ισοδυναμία". Εισαγωγή Στα μαθηματικά, σχέση ισοδυναμίας ονομάζεται μια σχέση που καθορίζει ποια στοιχεία ενός συνόλου είναι ισοδύναμα μεταξύ τους, ως προς τη σχέση αυτή. Έτσι, μια σχέση ισοδυναμίας διαμερίζει ένα σύνολο σε ανά δύο ξένα υποσύνολα, όπου κάθε υποσύνολο περιέχει τα μεταξύ τους ισοδύναμα στοιχεία. Τα υποσύνολα αυτά ονομάζονται κλάσεις ισοδυναμίας. Ορισμός Μια σχέση σε ένα σύνολο Α ονομάζεται σχέση ισοδυναμίας ανν είναι ανακλαστική, συμμετρική και μεταβατική. Δηλαδή ανν για κάθε a, b, c στο Α ισχύουν: : a\sim a\quad : a\sim b\quad\iff\quad b\sim a : a\sim b , b\sim c\Longrightarrow a\sim c. Συμβολισμός Αν και οι διάφοροι συμβολισμοί που χρησιμοποιούνται σε όλη τη βιβλιογραφία για να υποδηλώσουν ότι δύο στοιχεία α και β ενός συνόλου είναι ισοδύναμα,είναι ισοδύναμοι, οι πιο κοινοί είναι «α ~ b" και "a ≡ b",οι οποίοι χρησιμοποιούνται όταν το R είναι η προφανής σχέση που αναφέρεται, και παραλλαγές της «α ~ R b", "α ≡ R b" ή "aRb" αλλιώς. Παραδείγματα Απλό παράδειγμα Ας είναι \{a,b,c\} ένα σύνολο με μια σχέση ισοδυναμίας \{(a,a),(b,b),(c,c),(b,c),(c,b)\} .Για αυτή τη σχέση οι κλάσεις ισοδυναμίας είναι: a=\{a\} ~~~~ b=c=\{b,c\} Σύνολο όλων των κλάσεων ισοδυναμίας για αυτή τη σχέση είναι \{\{a\},\{b,c\}\} . Σχέσεις Ισοδυναμίας Ακολουθούν όλες οι σχέσεις ισοδυναμίας: * "Είναι ίσο με" για το σύνολο των πραγματικών αριθμών. *"Έχει τα ίδια γενέθλια, όπως" για το σύνολο όλων των ανθρώπων. *"Είναι παρόμοια με" για το σύνολο όλων των τριγώνων. *"Είναι σύμφωνες με το" για το σύνολο όλων των τριγώνων. *"Είναι σύμφωνες με,τη μορφή n" για τους ακέραιους. *"Έχει την ίδια εικόνα με μια συνάρτηση" σχετικά με τα στοιχεία του τομέα της συνάρτησης. *»Έχει την ίδια απόλυτη τιμή» για το σύνολο των πραγματικών αριθμών. *"Έχει το ίδιο συνημίτονο" για το σύνολο όλων των γωνιών. *"Είναι παράλληλα" για το σύνολο των υποχώρων ενός γενικευμένου χώρου. Σχέσεις που δεν είναι ισοδυναμίες *Η σχέση "≥" μεταξύ των πραγματικών αριθμών είναι ανακλαστική και μεταβατική, αλλά δεν είναι συμμετρική. Για παράδειγμα, 7 ≥ 5 δεν συνεπάγεται ότι 5≥7. Είναι, ωστόσο, μια μερική σειρά. *Η σχέση "έχει ένα κοινό παράγοντα μεγαλύτερο από 1 με το" μεταξύ των φυσικών αριθμών μεγαλυτέρων από 1, είναι ανακλαστική και συμμετρική, αλλά δεν είναι μεταβατική. (Παράδειγμα: Οι φυσικοί αριθμοί 2 και 6 έχουν ένα κοινό παράγοντα μεγαλύτερο από 1, και 6 και 3, έχουν ένα κοινό παράγοντα μεγαλύτερο από 1, αλλά 2 και 3 δεν έχουν ένα κοινό παράγοντα μεγαλύτερο από 1). *Η κενή σχέση R σε ένα μη κενό σύνολο X (δηλαδή aRb δεν είναι αληθές) είναι συμμετρική και μεταβατική, αλλά δεν είναι ανακλαστική. (Εάν το Χ είναι επίσης κενό τότε η R είναι αυτοπαθής.) *Η σχέση "είναι περίπου ίση με" μεταξύ των πραγματικών αριθμών, ακόμη και εάν ορίζεται με μεγαλύτερη ακρίβεια, δεν είναι μια σχέση ισοδυναμίας, επειδή αν και ανακλαστική και συμμετρική, δεν είναι μεταβατική, δεδομένου ότι πολλαπλές μικρές αλλαγές μπορούν να συσσωρεύονται για να γίνει μια μεγάλη αλλαγή. Ωστόσο, εάν η προσέγγιση ορίζεται ασυμπτωτικά, για παράδειγμα, λέγοντας ότι δύο συναρτήσεις f και g είναι περίπου ίσες κοντά κάποιο σημείο, αν το όριο των f-g είναι μηδέν σε εκείνο το σημείο, τότε αυτό ορίζει μια σχέση ισοδυναμίας. *Η σχέση "είναι αδέλφια του» (που χρησιμοποιείται για να υποδηλώσει τα ζεύγη των ανθρώπων που έχουν τους ίδιους γονείς) για το σύνολο όλων των ανθρώπων δεν είναι μια σχέση ισοδυναμίας. Αν η σχέση είναι συμμετρική (αν Α είναι ένα αδελφός του Β, τότε το Β είναι αδελφός του Α) και μεταβατική για κάθε 3 ξεχωριστούς ανθρώπους (αν A είναι ένας αδελφός του Β και Γ είναι αδελφός του Β, τότε ο Α είναι ένας αδελφός του C, με την προϋπόθεση να μην είναι ο C (Σημειώστε ότι η "είναι αδέλφια του" δεν είναι μια μεταβατική σχέση, δεδομένου ότι ARB, και BRA συνεπάγεται ARA από την μεταβατικότητα)), δεν είναι ανακλαστική (α δεν μπορεί να είναι αδελφός του α). Η μικρή τροποποίηση, "είναι αδέλφια του, ή είναι το ίδιο πρόσωπο», είναι μια σχέση ισοδυναμίας. Συνδέσεις με άλλες σχέσεις *Μια μερική διάταξη είναι μια σχέση που είναι ανακλαστική, αντισυμμετρική και μεταβατική. *Μια σχέση αντιστοιχίας είναι μια σχέση ισοδυναμίας της οποίας το πεδίο X είναι επίσης η βασική σειρά για μια αλγεβρική δομή, και η οποία σέβεται την πρόσθετη δομή. Σε γενικές γραμμές, οι σχέσεις ταύτισης παίζουν το ρόλο των πυρήνων των ομομορφισμών, και το πηλίκο μιας δομής με μια σχέση συμβατότητας μπορεί να σχηματιστεί. Σε πολλές σημαντικές περιπτώσεις, οι σχέσεις συμβατότητας έχουν μια εναλλακτική παράσταση, όπως υποδομές της δομής στην οποία ορίζονται. Π.χ. οι σχέσεις αντιστοιχίας για τις ομάδες αντιστοιχούν στις κανονικές υποομάδες. *Η ισότητα αποτελεί τόσο μια σχέση ισοδυναμίας και μια μερικής διάταξης. Η ισότητα είναι, επίσης, η μόνη σχέση σε ένα σύνολο που είναι ανακλαστική, συμμετρική και αντισυμμετρική. *Μια αυστηρή σχέση μερικής διάταξης είναι ανακλαστική, μεταβατική, και αντισυμμετρική. *Μια μερική σχέση ισοδυναμίας είναι μεταβατική και συμμετρική. Μεταβατική και συμμετρική συνεπάγεται και ανακλαστική αν και μόνο αν για όλα τα α ∈ X, υπάρχει μοναδικό b ∈ Χ τέτοιο, ώστε α ~ b. *Μία ανακλαστική και συμμετρική σχέση είναι μια σχέση εξάρτησης,αν είναι πεπερασμένη, και μια σχέση ανοχής, αν είναι άπειρη. *Μια δυαδική σχέση είναι ανακλαστική και μεταβατική. Καλά ορισμένη σχέση ισοδυναμίας Αν ~ είναι μια σχέση ισοδυναμίας στο Χ, και Ρ (χ) είναι μια ιδιότητα των στοιχείων του Χ, τέτοια ώστε οποτεδήποτε x ~ y, P (x) είναι αληθής εάν P (y) είναι αληθής, τότε η ιδιότητα P λέγεται καλά ορισμένη ή μία αμετάβλητη τάξη στο πλαίσιο της σχέσης ~. Μια συχνή συγκεκριμένη περίπτωση συμβαίνει όταν f είναι μία συνάρτηση από το Χ σε άλλο σύνολο Ψ.Εάν x1 ~ x2 συνεπάγεται f (x1) = f (x2), τότε f λέγεται ότι είναι ένας μορφισμός για ~, αναλλοίωτη κάτω από ~, ή απλά αμετάβλητη στο πλαίσιο ~. Αυτό συμβαίνει, π.χ. στη θεωρία χαρακτήρα των πεπερασμένων ομάδων. Η τελευταία αυτή περίπτωση με την συνάρτηση f μπορεί να εκφράζεται από ένα αντιμεταθετικό τρίγωνο. Μερικοί συγγραφείς χρησιμοποιούν "συμβιβάζομαι με ~" ή απλά "σέβομαι ~" αντί για "αναλλοίωτη κάτω από ~". Γενικότερα, μια συνάρτηση μπορεί να καθορίσει ισοδύναμα επιχειρήματα (κάτω από μια σχέση ισοδυναμίας ~ Α) σε ισοδύναμες τιμές (κάτω από μια σχέση ισοδυναμίας ~ B). Μια τέτοια λειτουργία είναι γνωστή ως ένα μορφισμός από ~Α στο ~Β. Κλάση ισοδυναμίας, σύνολο πηλίκου, διαμέριση Εστω X ένα μη κενό σύνολο, και έστω a,b\in X . Μερικοί ορισμοί: Κλάση ισοδυναμίας Το σύνολο όλων των α και β για τα οποία α ~ b συνθέτουν μια κλάση ισοδυναμίας του X από την ~. Έστω a := \{x \in X | x \sim a\} προσδιορίζει την ισοδυναμία κατηγορία στην οποία ανήκει το α. Στη συνέχεια, όλα τα στοιχεία του X είναι ισοδύναμα μεταξύ τους, όπως και τα στοιχεία της ίδιας κλάσης ισοδυναμίας. Σύνολο πηλίκου Το σύνολο όλων των πιθανών κλάσεων ισοδυναμίας του X συμβολίζεται με ~, X/\mathord{\sim} := \{x | x \in X\} , είναι το πηλίκο του X από ~. Αν X είναι ένας τοπολογικός χώρος, υπάρχει ένας φυσικός τρόπος για να μετατρέψει το X / ~ σε ένα τοπολογικό χώρο. Αντιστοιχία Η προβολή της ~ είναι η συνάρτηση \pi: X \to X/\mathord{\sim} που ορίζεται \pi(x) = x από την οποία καθορίζονται τα στοιχεία του Χ στις αντίστοιχες κλάσεις ισοδυναμίας τους με ~. Θεώρημα σχετικά με τις αντιστοιχίες: Ας τη συνάρτηση f: X → B είναι τέτοια ώστε α ~ b → f (α) = f (β). Στη συνέχεια, υπάρχει μια μοναδική συνάρτηση g: X / ~ → B, τέτοια ώστε f = gπ. Αν f είναι μία surjection και α ~ b ↔ f (α) = f (β), τότε το G είναι μια αμφιμονοσήμαντη αντιστοιχία. Ισοτιμία πυρήνα Η ισοτιμία του πυρήνα της συνάρτησης f είναι η ισοδυναμία ~ σχέση που ορίζεται από x\sim y \iff f(x) = f(y) . Η ισοτιμία του πυρήνα είναι μια ένα προς ένα ταυτοτική σχέση. Διαμέριση Ένα διαμέρισμα του X είναι ένα σύνολο P των πεπερασμένων υποσυνόλων του X, τέτοιο ώστε κάθε στοιχείο του X είναι ένα στοιχείο ενός στοιχείου του P. Κάθε στοιχείο του P είναι ένα μέρος του διαμερίσματος. Επιπλέον, τα στοιχεία του P είναι ανά δύο ξένα μεταξύ τους και η ένωσή τους είναι το Χ. Έστω X ένα πεπερασμένο σύνολο με n στοιχεία. Δεδομένου ότι κάθε σχέση ισοδυναμίας πάνω στο Χ αντιστοιχεί σε ένα διαμέρισμα του Χ, και αντιστρόφως, ο αριθμός των πιθανών σχέσεων ισοδυναμίας στο X ισούται με τον αριθμό των διακριτών χωρισμάτων του X, το οποίο είναι το νιοστό Bn αριθμός Bell : B_n = \frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}, όπου τα παραπάνω είναι ένας από τους τρόπους για να γράψει το νιοστό αριθμό Bell Θεμελιώδες θεώρημα της ισοδυναμίας σχέσεων Ένα βασικό αποτέλεσμα συνδέει σχέσεις ισοδυναμίας και διαμερίσεις: *Μια σχέση ισοδυναμίας ~ σε ένα σύνολο X,είναι διαμερίσεων X. *Αντίθετα, αντιστοίχως σε κάθε διαμέρισμα του X, υπάρχει μια σχέση ισοδυναμίας ~ στο Χ. Σε αμφότερες τις περιπτώσεις, τα μέρη του διαμερίσματος του Χ είναι οι κλάσεις ισοδυναμίας ~ του Χ. Δεδομένου ότι κάθε στοιχείο του Χ ανήκει σε ένα μοναδικό μέρος οποιουδήποτε διαμερίσματος του Χ, και δεδομένου ότι κάθε μέρος του διαμερίσματος είναι ταυτόσημο με μία κλάση ισοδυναμίας ~ του Χ, κάθε στοιχείο του Χ ανήκει σε μια μοναδική κατηγορία ισοδυναμίας ~ του Χ. Έτσι, υπάρχει μια φυσική αμφιμονοσήμαντη αντιστοιχία από το σύνολο όλων των πιθανών σχέσεων ισοδυναμίας για το Χ και για το σύνολο όλων των χωρισμάτων του Χ. Συγκρίνοντας τις σχέσεις ισοδυναμίας Αν ~ και ≈ είναι δύο σχέσεις ισοδυναμίας στο ίδιο σύνολο S, και α ~ β συνεπάγεται α ≈ β για όλους α, β ∈ S, τότε ≈ λέγεται ότι είναι μία δυνατότερη σχέση από ~, και ~ είναι μια πιο αδύναμη σχέση από ≈ .Ισοδύναμα, *~ είναι πιο αδύναμο από ≈ αν κάθε κλάση ισοδυναμίας της ~ είναι ένα υποσύνολο μιας κλάσης ισοδυναμίας της ≈, και έτσι κάθε κλάση ισοδυναμίας της ≈ είναι μια ένωση των κλάσεων ισοδυναμίας της ~. *~ είναι λεπτότερο από ≈ αν το διαμέρισμα που δημιουργήθηκε από ~ είναι μια διαίρεση του διαμερίσματος που δημιουργήθηκε από ≈. Η ισότητα ως σχέση ισοδυναμίας είναι η καλύτερη σχέση ισοδυναμίας για οποιοδήποτε σύνολο, ενώ η τετριμμένη σχέση που κάνει όλα τα ζεύγη των στοιχείων που σχετίζονται είναι η δυνατότερη. Δημιουργία σχέσεων ισοδυναμίας *Για κάθε σύνολο X, υπάρχει μια σχέση ισοδυναμίας για το σύνολο → X όλων των δυνατών συναρτήσεων X → X. Οι δύο αυτές συναρτήσεις θεωρούνται ισοδύναμες όταν αντίστοιχες σειρές τους έχουν τον ίδιο πληθάριθμο. Συναρτήσεις ισοδύναμες με τον τρόπο αυτό σχηματίζουν μία κλάση ισοδυναμίας για → X, και αυτές οι κλάσεις ισοδυναμίας, χώρισμα → X. *Η τομή της κάθε συλλογής σχέσεων ισοδυναμίας πάνω στο Χ (θεωρείται ως ένα υποσύνολο του X × X) είναι επίσης μια σχέση ισοδυναμίας. Αυτό παρέχει ένα βολικό τρόπο για να παράγει μια σχέση ισοδυναμίας: Για οποιαδήποτε δυαδική σχέση R στο X, η σχέση ισοδυναμίας που παράγεται από την R είναι η μικρότερη σχέση ισοδυναμίας που περιέχει R. Συγκεκριμένα,η R δημιουργεί την σχέση ισοδυναμίας a ~ b αν και μόνο αν υπάρχουν στοιχεία x1, x2, ..., Χn τέτοια, ώστε a = x1, b = Xn, και (xi, xi + 1) ∈ R ή (xi +1, xi) ∈ R, i = 1, ..., n -1. Σημειώστε ότι η σχέση ισοδυναμίας που παράγεται με τον τρόπο αυτό μπορεί να είναι ασήμαντη. Για παράδειγμα, η σχέση ισοδυναμίας ~ παράγεται από: *Οποιαδήποτε συνολική τάξη στο X έχει ακριβώς μία κλάση ισοδυναμίας, X ίδια, επειδή x ~ y για κάθε x και y *Κάθε υποσύνολο της σχέσης ταυτότητας X έχει κλάσεις ισοδυναμίας που είναι οι μοναδικές της X. *Σχέσεις Ισοδυναμίας μπορούν να κατασκευάσουν νέους χώρους από το "κόλλημα πραγμάτων μαζί." Έστω X η μονάδα καρτεσιανού τετραγώνου 0,1 × 0,1, και έστω ~ είναι η σχέση ισοδυναμίας στο X που ορίζεται ∀ a, b ∈ 0,1 ((a, 0) ~ (α, 1) ∧ (0, b) ~ (1, β)). Στη συνέχεια, ο χώρος πηλίκου X / ~ μπορεί φυσικά να ταυτισθεί με ένα δακτύλιο: παίρνει ένα τετράγωνο τμήμα χάρτου, κόβει και κολλά μαζί το άνω και κάτω άκρο για να σχηματίσει έναν κύλινδρο, τότε λυγίσει τον κύλινδρο, έτσι ώστε να κολλά μαζί τα δύο ανοικτά άκρα του, με αποτέλεσμα ένα δακτύλιο. Αλγεβρική δομή Ένα μεγάλο μέρος των μαθηματικών στηρίζεται στη μελέτη των ισοδυναμιών, και τις σχέσεις τάξης. Η θεωρία των πλεγμάτων συλλαμβάνει την μαθηματική δομή των σχέσεων τάξης. Ακόμη κι αν σχέσεις ισοδυναμίας είναι τόσο συχνές στα μαθηματικά και τις σχέσεις τάξης, η αλγεβρική δομή των ισοδυναμιών δεν είναι τόσο γνωστή όσο εκείνη των τάξεων. Η πρώην δομή βασίζεται κατά κύριο λόγο στην θεωρία των ομάδων και, σε μικρότερο βαθμό, στη θεωρία των πλεγμάτων και στην Κατηγοροθεωρία. Θεωρία ομάδων'' Ακριβώς όπως οι σχέσεις θεμελιώνονται σε διατεταγμένα σύνολα, σύνολα στο πλαίσιο των ζευγών supremum και infimum, οι σχέσεις ισοδυναμίας στηρίζονται σε κατανεμημένα σύνολα, τα οποία είναι κλειστά σύνολα και διατηρούν την δομή και την διαμέρισή τους. Δεδομένου ότι όλες αυτές οι διαμερίσεις καθορίζουν μια κλάση ισοδυναμίας, οι εν λόγω διαμερίσεις έχουν παραλλαγές. Ως εκ τούτου, παραδείγματα ομάδων (επίσης γνωστός μετασχηματισμός ομάδων) αποτελεί η σχετική έννοια της τροχιάς σχετικά με την μαθηματική δομή των σχέσεων ισοδυναμίας. Έστω" ~ " δηλώνει μια σχέση ισοδυναμίας πάνω για κάποιο μη κενό σύνολο A,το οποίο ονομάζεται υποκείμενο σύνολο. Έστω G συνάρτηση που χαρακτηρίζει το σύνολο Α και διατηρεί τη δομή του διαμερίσματος του Α: ∀ x ∈ A ∀ g ∈ G (g (x) ∈ x). Στη συνέχεια, ισχύουν τα ακόλουθα τρία συνδεδεμένα θεωρήματα: *~ Χωρίσματα Α σε κλάσεις ισοδυναμίας. (Αυτό είναι το θεμελιώδες θεώρημα των σχέσεων ισοδυναμίας που αναφέρθηκαν παραπάνω) *Λαμβάνοντας υπόψη ένα κομμάτι του Α, G είναι μια ομάδα μετασχηματισμού σύμφωνα με τη σύνθεση, των οποίων οι τροχιές είναι τα μέρη του κομματιού *Λαμβάνοντας υπόψη μια αλλαγή της ομάδας G πάνω στο Α, υπάρχει μια σχέση ισοδυναμίας ~ πάνω αστο Α, του οποίου οι κλάσεις ισοδυναμίας είναι οι τροχιές των G. Εν ολίγοις, δίνεται μια σχέση ισοδυναμίας ~ πάνω στο Α, υπάρχει μια ομάδα μετασχηματισμού G πάνω στο A της οποίας η τροχιά είναι οι κλάσεις ισοδυναμίας της Α ~. Ο χαρακτηρισμός μεταμόρφωση της ομάδας των σχέσεων ισοδυναμίας διαφέρει ριζικά από τον τρόπο που χαρακτηρίζονται τα πλέγματα κλάσεων ισοδυναμίας. Τα επιχειρήματα της θεωρίας των πλεγμάτων ενώνονται και εντάσσονται ως στοιχεία ενός συνόλου Α. σύμπαντος Εν τω μεταξύ, τα επιχειρήματα των εργασιών της ομάδας μετασχηματισμού είναι στοιχεία ενός συνόλου διαμερίσεων, A → A. Η μετακίνηση σε ομάδες σε γενικές γραμμές, εστω H είναι μια υποομάδα κάποιας ομάδας G. Ας είναι ~ μια σχέση ισοδυναμίας στο G, όπως και α ~ b ↔ (ab-1 ∈ H). Οι κλάσεις ισοδυναμίας της ~-που ονομάζονται επίσης τροχιές της δράσης του H στο G-είναι τα σωστά ομοσύνολα της H στην G. Ας είναι σύνθετη συνάρτηση που θα ερμηνεύσει τον πολλαπλασιασμό της ομάδας, και αντίστροφη συνάρτηση θα ερμηνεύσει την αντίστροφη ομάδας. Στη συνέχεια, G είναι μια ομάδα με σύνθεση, πράγμα που σημαίνει ότι ∀ x ∈ A ∀ g ∈ G ([g (x) = x), επειδή G πληρεί τις ακόλουθες τέσσερις προϋποθέσεις: *G είναι κλειστή ως προς τη σύνθεση. Η σύνθεση των οποιωνδήποτε δύο στοιχείων της G υπάρχει, επειδή ο τομέας και το πεδίο τιμών του κάθε στοιχείου του G είναι Α. *Ύπαρξη της ταυτοτικής συνάρτησης. Η ταυτοτική συνάρτηση, I (x) = x, αποτελεί ένα προφανές στοιχείο του G *Ύπαρξη αντίστροφης συνάρτησης. Κάθε συνάρτηση g έχει έναν αντίστροφο g-1, έτσι ώστε gg-1 = Ι *Προσεταιριστική ιδιότητα συναρτήσεων. f (GH) = (FG) h. Αυτό ισχύει για όλες τις συναρτήσεις σε όλους τους τομείς Έστω f και g να είναι οποιαδήποτε δύο στοιχεία του Γ. Δυνάμει του ορισμού του Ζ, (f (x)) = (x) και (x) = x, έτσι ώστε (f (x)) = χ. Ως εκ τούτου, το G είναι επίσης μια ομάδα μετασχηματισμού (και μία ομάδα αυτομορφισμού), καθώς η σύνθεσή συναρτήσεων διατηρεί την αυτονομία της. Κατηγορίες και Ομαδοποίηση Έστω G μια ομάδα και έστω ότι το "~" υποδηλώνει μια σχέση ισοδυναμίας πάνω στη G. Στη συνέχεια, μπορούμε να σχηματίσουμε μια ομάδα που θα εκπροσωπεί την σχέση ισοδυναμίας ως εξής. Τα αντικείμενα είναι τα στοιχεία της G, και για κάθε δύο στοιχεία x και y της G, υπάρχει ένας μοναδικός μορφισμός από το x προς y αν και μόνο αν x ~ y. Τα πλεονεκτήματα της σχετικά με μια σχέση ισοδυναμίας ως ειδική περίπτωση μίας ομάδας περιλαμβάνουν: *Ότι η έννοια της «ελεύθερης σχέσης ισοδυναμίας" δεν υπάρχει,στηρίζεται στο ότι μεταβαίνει από μια ελεύθερη ομάδα σε ένα κατευθυνόμενο γράφημα. Έτσι έχει νόημα να μιλάμε για μια «παρουσίαση μιας σχέσης ισοδυναμίας», δηλαδή, μια παρουσίαση της αντίστοιχης ομάδας. *Δέσμες των ομάδων, ομαδικές αγωγές, σύνολα και σχέσεις ισοδυναμίας μπορούν να θεωρηθούν ως ειδική περίπτωση της έννοιας της ομάδας, μια άποψη που υποδηλώνει μια σειρά από αναλογίες. *Οι πολλές περιπτώσεις "πηλίκων," και ως εκ τούτου οι κατάλληλες σχέσεις ισοδυναμίας που συχνά αποκαλoύνται μαθηματικές αναλογίες, είναι σημαντικές. Αυτό οδηγεί στην έννοια της εσωτερικής ομάδας σε μια κατηγορία. Πλέγματα Οι πιθανές σχέσεις ισοδυναμίας για κάθε σύνολο X, μετά από εντολή ένταξης στο σύνολο, αποτελούν ένα πλήρες πλέγμα, που ονομάζεται Con X κατά συνθήκη. Η κανονική ker καθορίζει: X ^ X → Con X, σχετίζεται με το μονοειδές Χ ^ Χ όλων των λειτουργιών X και Con X. ker είναι επί αλλά όχι ένα προς ένα. Λιγότερο τυπικά, η ισοδυναμία ker στο X, παίρνει κάθε συνάρτηση f: X → X στον πυρήνα του ker. Ομοίως, ker (ker) είναι μια σχέση ισοδυναμίας στο X ^ X. Σχέσεις ισοδυναμίας και μαθηματικής λογικής Οι σχέσεις ισοδυναμίας αποτελούν μια έτοιμη πηγή με παραδείγματα ή αντιπαραδείγματα. Για παράδειγμα, μια σχέση ισοδυναμίας με ακριβώς δύο άπειρες κλάσεις ισοδυναμίας είναι ένα εύκολο παράδειγμα μιας θεωρίας η οποία είναι ω-υποσύνολο, αλλά όχι υποσύνολο για οποιοδήποτε μεγαλύτερο αριθμό. Μια συνέπεια της θεωρίας μοντέλο είναι ότι οι ιδιότητες που καθορίζουν μια σχέση μπορούν να αποδειχθούν ανεξάρτητες μεταξύ τους (και ως εκ τούτου απαραίτητα μέρη του ορισμού) αν και μόνο αν, για κάθε ιδιότητα,τα παραδείγματα μπορούν να βρεθούν από τις σχέσεις που δεν πληρούν τη συγκεκριμένη ιδιότητα, ενώ ικανοποιούνται από όλες τις άλλες ιδιότητες. Ως εκ τούτου, οι τρεις καθορισμοί των ιδιοτήτων των σχέσεων ισοδυναμίας μπορούν να αποδειχθούν αμοιβαίως ανεξάρτητα από τα ακόλουθα τρία παραδείγματα: *Ανακλαστική και μεταβατική: Η σχέση ≤ στο Ν. *Συμμετρική και μεταβατική: Η σχέση R σε N, ορίζεται ως aRb ↔ ab ≠ 0. Ή οποιαδήποτε μερική σχέση ισοδυναμίας *Ανακλαστική και συμμετρική: Η σχέση R στο Ζ, ορίζεται ως aRb ↔ ". Α - β διαιρείται με τουλάχιστον ένα από τα 2 ή 3" Ή οποιαδήποτε σχέση εξάρτησης. Ιδιότητες προσδιορισμού σε πρώτης τάξης λογική για το ότι μια σχέση ισοδυναμίας μπορεί ή δεν μπορεί να κατέχει περιλαμβάνουν: *Ο αριθμός των κλάσεων ισοδυναμίας είναι πεπερασμένο ή άπειρο *Ο αριθμός των κλάσεων ισοδυναμίας ισούται με το (πεπερασμένο) φυσικό αριθμό n *Ο αριθμός των στοιχείων σε κάθε κλάση ισοδυναμίας είναι ο φυσικός αριθμός n. Ευκλείδειες σχέσεις Πράγματα που ισούται με το ίδιο πράγμα και ισοδυναμούν με ένα άλλο. Σήμερα, η ιδιότητα που περιγράφεται από την κοινή έννοια 1 ονομάζεται Ευκλείδεια (αντικαθιστώντας το "ίσο" από "είναι σε σχέση με το"). Το παρακάτω θεώρημα συνδέει Ευκλείδειες σχέσεις και σχέσεις ισοδυναμίας: Θεώρημα. Αν μια σχέση είναι Ευκλείδεια και ανακλαστική, είναι επίσης συμμετρική και μεταβατική. Απόδειξη: *(ARC ∧ BRC) → aRb / c = (ara ∧ BRA) → aRb διαγράψει T ∧ =BRA → ARB. Ως εκ τούτου, η R είναι συμμετρική *(ARC ∧ BRC) → aRb συμμετρία = (ARC ∧ CRB) → ARB. Ως εκ τούτου, η R είναι μεταβατική. Ως εκ τούτου, μια σχέση ισοδυναμίας είναι μια σχέση που είναι Ευκλείδεια και ανακλαστική. Υποσημειώσεις Εσωτερική Αρθρογραφία * Κλάση Ισοδυναμίας *κατηγορία *Μαθηματική Κλάση Βιβλιογραφία *Brown, Ronald, 2006. Topology and Groupoids. Booksurge LLC. ISBN 1-4196-2722-8. *Castellani, E., 2003, "Symmetry and equivalence" in Brading, Katherine, and E. Castellani, eds., Symmetries in Physics: Philosophical Reflections. Cambridge Univ. Press: 422-433. *Robert Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice Hall. Chpt. 12 discusses how equivalence relations arise in lattice theory. *Higgins, P.J., 1971. Categories and groupoids. Van Nostrand. Downloadable since 2005 as a TAC Reprint. *John Randolph Lucas, 1973. A Treatise on Time and Space. London: Methuen. Section 31. *Rosen, Joseph (2008) Symmetry Rules: How Science and Nature are Founded on Symmetry. Springer-Verlag. Mostly chpts. 9,10. *Raymond Wilder (1965) Introduction to the Foundations of Mathematics 2nd edition, Chapter 2-8: Axioms defining equivalence, pp 48–50, John Wiley & Sons. Ιστογραφία *Ομώνυμο άρθρο στην Βικιπαίδεια *Ομώνυμο άρθρο στην Livepedia *Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009 *Equivalence relation at PlanetMath Κατηγορία:Σχέσεις